// Copyright 2011 SUDO Team (UFMG)
// leonardoconegundes@gmail.com
// Reference: http://algorithmium.com/2010/07/19/sieve-of-eratosthenes/comment-page-1/

const int SIEVE_MAXN = 10000001;
const int SIEVE_SIZE = SIEVE_MAXN/16+1;
const int SIEVE_MAXPRIMES = 685000;  // 1.26 MAXN / log(MAXN);

char SIEVE_mark[SIEVE_SIZE];  // ( SIEVE_mark[n>>4]&(1<<((n>>1)&7)) ) == 0 se 2n+1 eh primo
char SIEVE_isPrime[SIEVE_MAXN];
int  SIEVE_primes[SIEVE_MAXPRIMES];


void sieve(bool isprime[], int n) {
  int i, j;
  int cntprimes;

  for (i = 3; i*i <= n; i += 2)
    if ( (SIEVE_mark[i>>4] & (1<<((i>>1)&7))) == 0 )
      for (j = i*i; j <= n; j += i<<1) SIEVE_mark[j>>4] |= (1<<((j>>1)&7));

  cntprimes = 0;
  SIEVE_primes[cntprimes++] = 2;

  for (i = 3; i <= n; i += 2)
    if ( (SIEVE_mark[i>>4]&(1<<((i>>1)&7))) == 0)
      SIEVE_primes[cntprimes++] = i;

  for (i = 0;i < cntprimes;i++)
    isprime[SIEVE_primes[i]] = true;
}
